Java তে Queue ইমপ্লিমেন্টেশন (using Array এবং Linked List)

Queue কি?

Queue হল একটি অ্যাবস্ট্র্যাক্ট ডেটা টাইপ (ADT) যা FIFO (First In, First Out) নীতি অনুসরণ করে। এর মানে হল যে প্রথমে যে উপাদানটি ইনসার্ট হবে, সেটিই প্রথমে আউটপুট হবে। এটি বাস্তব জীবনে ব্যবহারিক সমস্যাগুলির জন্য উপযোগী, যেমন প্রিন্টার জব, কল সেন্টার সিস্টেম, এবং প্রক্রিয়াকরণ সিস্টেমের জন্য।

Queue মূলত দুটি প্রধান অপারেশন সাপোর্ট করে:

1. enqueue (ইনসার্ট): একটি উপাদান কোয়েতে যোগ করা।
2. dequeue (ডিলিট): কোয়েত থেকে একটি উপাদান সরানো।

এছাড়া, peek অপারেশনও থাকে যা কোয়েরির প্রথম উপাদান দেখাতে সাহায্য করে এবং isEmpty অপারেশন কোয়েটি খালি কিনা তা চেক করে।

1. Queue ইমপ্লিমেন্টেশন using Array

এখানে Array ব্যবহার করে একটি Queue ইমপ্লিমেন্ট করার উদাহরণ দেখানো হচ্ছে। আমরা একটি নির্দিষ্ট সাইজের অ্যারে ব্যবহার করব যা সীমাবদ্ধ থাকবে।

উদাহরণ: Queue ইমপ্লিমেন্টেশন using Array

public class QueueUsingArray {
    private int[] queue;
    private int front, rear, size;

    // Constructor to initialize queue
    public QueueUsingArray(int capacity) {
        queue = new int[capacity];
        size = 0;
        front = 0;
        rear = -1;
    }

    // Enqueue operation
    public void enqueue(int value) {
        if (size == queue.length) {
            System.out.println("Queue is full");
            return;
        }
        rear = (rear + 1) % queue.length; // Circular increment
        queue[rear] = value;
        size++;
    }

    // Dequeue operation
    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return -1;
        }
        int value = queue[front];
        front = (front + 1) % queue.length; // Circular increment
        size--;
        return value;
    }

    // Peek operation
    public int peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return -1;
        }
        return queue[front];
    }

    // Check if queue is empty
    public boolean isEmpty() {
        return size == 0;
    }

    // Display the queue elements
    public void display() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return;
        }
        int i = front;
        while (i != rear) {
            System.out.print(queue[i] + " ");
            i = (i + 1) % queue.length;
        }
        System.out.println(queue[rear]);
    }
}

public class Main {
    public static void main(String[] args) {
        QueueUsingArray queue = new QueueUsingArray(5);

        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.enqueue(40);
        queue.enqueue(50);
        
        System.out.println("Queue elements:");
        queue.display();  // Output: 10 20 30 40 50

        System.out.println("Dequeue element: " + queue.dequeue());  // Output: 10
        queue.display();  // Output: 20 30 40 50
        
        System.out.println("Peek element: " + queue.peek());  // Output: 20
    }
}

ব্যাখ্যা:

• Enqueue: কোয়েতে একটি উপাদান যোগ করা হয়, তবে যদি কোয়ে পূর্ণ থাকে, এটি একটি ত্রুটি বার্তা প্রদর্শন করবে।
• Dequeue: কোয়েতে প্রথম উপাদান সরিয়ে ফেলা হয় এবং এটি সার্বিক সাইজ কমিয়ে দেয়।
• Peek: প্রথম উপাদানটি কেবল দেখা হয়, তবে এটি কোয়েত থেকে সরানো হয় না।
• Circular Queue: এখানে সাইক্লিক আর্গুমেন্ট ব্যবহার করা হয়েছে, যাতে কোয়েতে স্থান পূর্ণ হওয়ার পরও পুরনো স্থানে নতুন উপাদান যোগ করা যায়।

2. Queue ইমপ্লিমেন্টেশন using Linked List

এখন আমরা Linked List ব্যবহার করে একটি Queue ইমপ্লিমেন্ট করব। Linked List-based Queue একটি dynamic queue হতে পারে, যেটি কোনো নির্দিষ্ট সাইজের সীমা ছাড়াই কাজ করতে পারে।

উদাহরণ: Queue ইমপ্লিমেন্টেশন using Linked List

public class QueueUsingLinkedList {
    private Node front, rear;
    private int size;

    // Node class
    private class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    // Constructor
    public QueueUsingLinkedList() {
        front = rear = null;
        size = 0;
    }

    // Enqueue operation
    public void enqueue(int value) {
        Node newNode = new Node(value);
        if (rear == null) {
            front = rear = newNode;
            return;
        }
        rear.next = newNode;
        rear = newNode;
    }

    // Dequeue operation
    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return -1;
        }
        int value = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        size--;
        return value;
    }

    // Peek operation
    public int peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return -1;
        }
        return front.data;
    }

    // Check if queue is empty
    public boolean isEmpty() {
        return front == null;
    }

    // Display the queue elements
    public void display() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return;
        }
        Node temp = front;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        QueueUsingLinkedList queue = new QueueUsingLinkedList();

        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.enqueue(40);
        
        System.out.println("Queue elements:");
        queue.display();  // Output: 10 20 30 40

        System.out.println("Dequeue element: " + queue.dequeue());  // Output: 10
        queue.display();  // Output: 20 30 40
        
        System.out.println("Peek element: " + queue.peek());  // Output: 20
    }
}

ব্যাখ্যা:

• Node class: Node ক্লাসে প্রতিটি নোডের জন্য ডেটা এবং পরবর্তী নোডের রেফারেন্স থাকে।
• Enqueue: যখন নতুন উপাদান ইনসার্ট করা হয়, তখন একটি নতুন নোড তৈরি করা হয় এবং রিয়ার পয়েন্টার সেট করা হয়।
• Dequeue: ফ্রন্ট নোড থেকে উপাদান সরিয়ে ফেলা হয় এবং ফ্রন্ট পয়েন্টার আপডেট করা হয়।
• Peek: ফ্রন্ট নোডের ডেটা দেখানো হয়, কিন্তু এটি কোয়েত থেকে সরানো হয় না।
• Display: লিঙ্কড লিস্ট ট্রাভার্স করে কোয়েরির উপাদানগুলো প্রদর্শন করা হয়।

3. Singly Linked List Queue vs Array-based Queue

সারাংশ

Queue হল একটি গুরুত্বপূর্ণ ডেটা স্ট্রাকচার যা FIFO (First In, First Out) নীতি অনুসরণ করে। আমরা Array এবং Linked List ব্যবহার করে Queue ইমপ্লিমেন্ট করতে পারি। Array-based Queue সীমাবদ্ধ আকারে কাজ করে, তবে Linked List-based Queue ডাইন

ামিক এবং সুবিধাজনক হতে পারে। ডেটা স্ট্রাকচার এবং অ্যালগরিদম এর মধ্যে কোড অপটিমাইজেশন এবং অ্যাক্সেসের ক্ষেত্রে দুটি পদ্ধতিরই নিজস্ব সুবিধা ও সীমাবদ্ধতা রয়েছে।